package com.lxl.radix;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Description 基数排序
 * @Date 2021/8/24 21:29
 * @Created by LXLDEMO
 */
public class RadixSort {
    public static void main(String[] args) {
        // 测试数据
        int[] arr = {37,18,21,21,49,0,25,6,14,-21};

        // 有问题
//        int[] ints = RadixSort(arr);
//        System.out.println("排序后"+Arrays.toString(ints));

        // 有问题 测试输出
//        radixSort(arr,arr.length);

        // 可正常排序，但只支持非负数
//        radixSort(arr);
    }

    /**
     * 辅助函数 求数据的最大位数
     * @param data
     * @param n
     */
    public static int maxBit(int data[],int n){
        // 保存最大的位数
        int d = 1;
        int p = 10;
        for (int i = 0;i<n;i++){
            while (data[i] >= p){
                p *= 10;
                ++d;
            }
        }
        return d;
    }

    /**
     * 基数排序
     * @param arr
     * @param len
     */
    public static void radixSort(int arr[],int len){
        // 找到数组中的最大位数
        int bit = maxBit(arr,arr.length);
        // 创建临时数组 用于接收排序的数据
        int[] tempArr = new int[len];
        // 0~9 (桶的数量：10)
        int[] countArr = new int[10];
        int radix = 1;

        for (int i = 1;i <= bit;i++){
            // 统计每一位数组出现次数 arr[j]的最低位：个位
            for (int j = 0;j<len;j++){
                int k = (arr[j]/radix)%10;
                System.out.println(arr[j]+" "+k);
                countArr[k]++;
            }
            System.out.println("出现次数"+Arrays.toString(countArr));

            // 将出现次数转换成排序后位置
            for (int j = 1;j<10;j++){
                countArr[j] = countArr[j-1] + countArr[j];
            }
            System.out.println("排序后的数据"+Arrays.toString(countArr));

            // 将元素根据位置存放到临时数组中
            for (int j = len -1;j>=0;j--){
                int k = (arr[j]/radix)%10;
                // todo:
                System.out.println(k+" "+ j +" "+ arr[j]);
                System.out.println(" "+countArr[k]);
                tempArr[countArr[k]-1] = arr[j];
                countArr[k]--;
                System.out.println("内部输出测试"+Arrays.toString(countArr));
            }
            System.out.println("第二次排序后"+Arrays.toString(countArr));

            // 将临时数组的内容复制到原数组中
            for (int j=0;j<len;j++){
                arr[j] = tempArr[j];
            }
            radix = radix * 10;
            System.out.println("本次排序结果："+ Arrays.toString(arr));
        }
    }





    private static void radixSort(int[] arr) {
        //待排序列最大值
        int max = arr[0];
        int exp;//指数

        //计算最大值
        for (int anArr : arr) {
            if (anArr > max) {
                max = anArr;
            }
        }

        //从个位开始，对数组进行排序
        for (exp = 1; max / exp > 0; exp *= 10) {
            //存储待排元素的临时数组
            int[] temp = new int[arr.length];
            //分桶个数
            int[] buckets = new int[10];

            //将数据出现的次数存储在buckets中
            for (int value : arr) {
                //(value / exp) % 10 :value的最底位(个位)
                buckets[(value / exp) % 10]++;
            }

            //更改buckets[i]，
            for (int i = 1; i < 10; i++) {
                buckets[i] += buckets[i - 1];
            }

            //将数据存储到临时数组temp中
            for (int i = arr.length - 1; i >= 0; i--) {
                temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
                buckets[(arr[i] / exp) % 10]--;
            }

            //将有序元素temp赋给arr
            System.arraycopy(temp, 0, arr, 0, arr.length);
        }

    }


    public static int[] RadixSort(int[] arr){
        if(arr.length == 0 || arr.length ==1) {
            return arr;
        }
        // max 指数组中最大的数，maxDigit 指这个最大的数是几位数
        int max = arr[0];
        for(int x:arr) {
            max = Math.max(x, max);
        }
        int maxDigit = 0;
        while(max != 0){
            max /= 10;
            maxDigit++;
        }
        // mod 用于为数组中的数取余数，div 用于把通过 mod 取的余数变成个位数
        int mod = 10;
        int div = 1;
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();
        for(int j = 0;j < 10;j++){
            bucket.add(new ArrayList<Integer>());
        }
        for(int i = 0;i<maxDigit;i++,mod *= 10,div *= 10){
            // 打印这一轮的排序结果
            System.out.println(Arrays.toString(arr));
            for(int j = 0;j < arr.length;j++){
                // num 指当前元素 arr[j] 的个/十/百/千位是几
                int num = (arr[j] % mod) / div;
                bucket.get(num).add(arr[j]);
            }
            int index = 0;
            for(int j = 0;j < 10;j++){
                if(bucket.get(j).size() != 0){
                    for(int x:bucket.get(j)) {
                        arr[index++] = x;
                    }
                    // 将桶中所有的动态数组清空，否则第二次循环开始再用到这些动态数组时里面还会有数据
                    bucket.get(j).clear();
                }
            }
        }
        return arr;
    }

}